10078 - The Art Gallery/p10078.cpp

   1 #include <iostream>
   2 #include <algorithm>
   3 #include <vector>
   4
   5 using namespace std;
   6
   7 struct Point{
   8   int x, y;
   9   bool operator < (const Point &p) const {
  10     return (x < p.x || (x == p.x && y < p.y));
  11   }
  12 };
  13
  14 // 2D cross product.
  15 // Return a positive value, if OAB makes a counter-clockwise turn,
  16 // negative for clockwise turn, and zero if the points are collinear.
  17 int cross(const Point &O, const Point &A, const Point &B)
  18 {
  19         return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
  20 }
  21
  22 // Returns a list of points on the convex hull in counter-clockwise order.
  23 // Note: the last point in the returned list is the same as the first one.
  24 vector<Point> convexHull(vector<Point> P)
  25 {
  26         int n = P.size(), k = 0;
  27         vector<Point> H(2*n);
  28
  29         // Sort Points lexicographically
  30         sort(P.begin(), P.end());
  31
  32         // Build lower hull
  33         for (int i = 0; i < n; i++) {
  34                 while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
  35                 H[k++] = P[i];
  36         }
  37
  38         // Build upper hull
  39         for (int i = n-2, t = k+1; i >= 0; i--) {
  40                 while (k >= t && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
  41                 H[k++] = P[i];
  42         }
  43
  44         H.resize(k);
  45         return H;
  46 }
  47
  48 void printPnt(const Point &p){
  49   cout << "(" << p.x << "," << p.y << ")";
  50 }
  51
  52 int main(){
  53   int n;
  54   cin >> n;
  55   while (n){
  56     //procesar caso
  57     vector<Point> g(n);
  58     for (int i=0; i<n; ++i){
  59       int x, y;
  60       cin >> x >> y;
  61       g[i].x = x;
  62       g[i].y = y;
  63     }
  64     /*cout << "g.size() es: " << g.size() << endl;
  65     for (int i=0; i<n; ++i){
  66       printPnt(g[i]);
  67       cout << " ";
  68     }
  69     cout << endl; */
  70     vector<Point> chull = convexHull(g);
  71     /*cout << "chull.size() es: " << chull.size() << endl;
  72     for (int i=0; i<chull.size(); ++i){
  73       printPnt(chull[i]);
  74       cout << " ";
  75     }
  76     cout << endl;*/
  77     chull.pop_back();
  78     if (chull.size() == n){
  79       cout << "No\n";
  80     }else{
  81       cout << "Yes\n";
  82     }
  83     cin >> n;
  84   }
  85   return 0;
  86 }